Cryptographic operations involving primality testing generally feature preliminary, faster filtering, before subjecting prime candidates to more comprehensive, slower primality checks. As an example, generating RSA keys may involve initial “sieving”, typically dividing by the first N (small) prime numbers. If any of these primes divides the candidate, we have proven its composite nature.
A different approach to trial divisions with effectively the same primes is to find greatest common divisors (GCDs) of a table of large products of small primes and the prime candidate. If any of these GCDs produces a result that differs from 1 (i.e. the candidate and a table entry are not relative primes), we have proven the candidate to be composite. Building a table of long prime products (typically, products close to the size of candidates) reduces the number of trial divisions, but it requires a general-purpose library capable of arbitrary multiword arithmetic. Savings are still obtained, as table pre-computation reduces the number of divisions, but each GCD calculation requires multiword division.
We are looking for an efficient trial division of a long prime candidate, trying to find if one of a fixed set of small primes is a divisor (used in cryptographic algorithms, such as in RSA).